package demo.DataStrucAndAlgo.AlgorithmOfTen;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/7-08-07-15:25
 * @Description：demo.DataStrucAndAlgo.AlgorithmOfTen
 */
/*
数据求和匹配：{3,34,4,12,5,2}的数据中，给出一个待匹配的值n，问是否能从数据中任意取出几个数，使得之和等于n ?
 */
public class DP_3 {
    static int[] data = {3,34,4,12,5,2};
    public static void main(String[] args) {
        System.out.println(re_OPT(data.length-1,9));

        System.out.println(dp_OPT(data.length-1,9));
    }

    /**
     * 动态规划：非递归出在一组数据中，是否有相加之和为待匹配数的情况
     * @param i   数组索引
     * @param a   待匹配数
     * @return    true or false
     */
    public static boolean dp_OPT(int i, int a) {
        boolean[][] res = new boolean[data.length][a+1];
        boolean A,B;
        for (int x = 0; x < res.length; x++) {
            for (int y = 0; y < a + 1; y++) {
                if(y == 0){
                    res[x][y] = true;
                }
                if(x==0 && y == data[0]){
                    res[x][y] = true;
                }
            }
        }
        for (int x = 1; x < res.length; x++) {
            for (int y = 1; y < a + 1; y++) {
                if(data[x] > y){
                    res[x][y] = res[x-1][y];
                }else{
                    A = res[x-1][y-data[x]];
                    B = res[x-1][y];
                    res[x][y] = A || B;
                }
            }
        }
        return res[i][a];
    }

    /**
     * 动态规划：递归求出在一组数据中，是否有相加之和为待匹配数的情况
     * @param i    数组索引
     * @param a    待匹配数
     * @return        true  or   false
     */
    public static boolean re_OPT(int i, int a) {
        if(a == 0){
            return true;
        }else if(i == 0){
            return data[i] == a;
        }else if( data[i] > a){
            return re_OPT(i-1,a);
        }
        return re_OPT(i-1,a-data[i]) || re_OPT(i-1,a);
    }
}
